package com.practice.niuke.new_direct_basics.class11;

/**
 * Manacher算法解决的问题
 * 字符串str中， 最长回文子串的长度如何求解？
 * 如何做到时间复杂度O(N)完成？
 */
public class Code02_Manacher {

    /**
     * 将源字符串处理成Manacher字符数组,
     * 例如，"1221" ---> "#1#2#2#1#"
     *
     * @param str 源字符串
     * @return char[]
     */
    public static char[] manacherString(String str) {
        char[] charArr = str.toCharArray();
        char[] res = new char[str.length() * 2 + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : charArr[index++];
        }
        return res;
    }

    public static int maxLcpsLength(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        // 将源字符串处理成Manacher字符数组,
        // 1221 ->  #1#2#2#1#
        char[] str = manacherString(s);
        // 回文半径数组，每个位置的值是字符数组中以该位置的字符为中心的最大回文半径
        int[] pArr = new int[str.length];
        // 讲述中：R代表最右边的扩成功的位置，代码中：最右的扩成功位置的，再下一个位置
        // 回文右边界的再往右一个位置    最右的有效区是R-1位置
        int R = -1;
        // 中心，取得最大回文半径时的中心位置，R更新C就更新，R不跟新C就不跟新
        int C = -1;
        // 扩出来的最大值
        int max = Integer.MIN_VALUE;
        // 每一个位置都求回文半径
        for (int i = 0; i != str.length; i++) {
            // i位置扩出来的答案，位置扩的区域，至少是多大；
            // R > i表示i在R内，
            // 2 * C - i表示i’位置，
            // pArr[2 * C - i]表示i'位置的回文半径，
            // R - i表示i到“最大回文半径右边界位置”的距离；
            // i至少的回文区域，先给pArr[i]
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            // 得到“i至少的回文区域”后再向左右两边扩，
            // i + pArr[i]为右边要验的位置，i - pArr[i]为左边要验的位置
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]])
                    // 右边要验的位置 和 左边要验的位置 的字符相等，扩成功
                    pArr[i]++;
                else {
                    // 扩失败
                    break;
                }
            }
            // i位置的回文右边界 是否超过 当前的最大回文右边界，
            // 有没有刷新R
            if (i + pArr[i] > R) {
                // 刷新R
                R = i + pArr[i];
                // 刷新C
                C = i;
            }
            max = Math.max(max, pArr[i]);
        }
        // 返回“最大回文半径-1”
        return max - 1;
    }

//	/**
//	 * Manacher的伪代码
//	 * @param s
//	 * @return
//	 */
//	public static int maxPlen(String s){
//		// 将源字符串处理成Manacher字符数组,
//		// "1221" ---> "#1#2#2#1#"
//		char[] str = manacherString(s);
//		// str的回文半径数组
//		int[] pArr = new int[str.length];
//		// 最长回文半径的右边界的位置
//		int R = -1;
//		// 取得最大回文半径时的中心位置，R更新C就更新，R不跟新C就不跟新
//		int C = -1;
//		// 求pArr每个位置的值
//		for (int i = 0; i < str.length; i++) {
//			if (i在R外){
//				// 失败1次
//				// 成功时，R一定变大
//				暴力扩;
//			}else {// i在R内
//				if (i'的回文区域在LR内部){
//					无成功和失败，直接出答案;
//				}else if (i'的回文区域在LR外部){
//					无成功和失败，直接出答案;
//				}else {// i'的回文区域的左边界刚好压在L上
//					// 失败1次
//					// 成功时，R一定变大
//					从R+1位置开始往外扩;
//				}
//			}
//		}
//
//		// pArr中最大值-1，返回
//	}

    public static void main(String[] args) {
        String str1 = "abc1234321ab";
        System.out.println(maxLcpsLength(str1));
    }

}
